- 综合排序
- 最热优先
- 最新优先
- 来自专栏Java架构师必看
堆排序（Heap Sort）
文章目录 算法描述 动图演示 代码实现 算法分析 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。 heapSort(array); System.out.println(Arrays.toString(array)); } 注意：这里用到了完全二叉树的部分性质 /** * Description: 堆排序
45630发布于 2021-07-13 - 来自专栏caoqi95的记录日志
C 语言实现堆排序 (Heap Sort)
堆排序是一种基于「堆」这一数据结构的排序算法。堆是一种近似完全二叉树的结构，分为大顶堆和小顶堆这两种。 大顶堆：子节点的值总是小于其父节点的值。 小顶堆：子节点的值总是大于其父节点的值。 堆排序：将顶端数据和最末尾数据交换位置，然后做最大堆调整的递归运算。 实现代码如下所示： ? 堆排序：将顶端数据和最末尾数据交换位置，然后做最小堆调整的递归运算。 实现代码如下所示： ? 具体代码可见这个 repo 中的 Homework-4 和 mid-exam。 参考： [1]. 堆排序 - 维基百科 [2]. 图解排序算法(三)之堆排序
1.9K30发布于 2019-05-13 - 来自专栏常用算法专栏
常用的排序算法之堆排序（Heap Sort）
堆排序（Heap Sort）起源 堆排序的概念由J.W.J. Williams在1964年提出，并在计算机科学中得到了广泛的应用。它利用了堆这种数据结构所具备的性质来实现排序。 定义 堆排序（Heap Sort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。 引伸义 堆排序算法可以看作是对直接选择排序的有效改进。 使用场景 堆排序适用于数据量较大且对空间复杂度要求不高的场景。由于其高效的时间复杂度，它经常被用于大数据排序等场景。 使用数据一步步举例 假设我们有一个数组 [4, 1, 3, 9, 7]，我们按照最大堆（父节点大于或等于子节点）的方式来进行堆排序。 建堆：首先将数组转换为最大堆。
47700编辑于 2025-04-05 - 来自专栏Java架构师必看
十大排序8–堆排序(Heap Sort）
堆排序 文章目录 堆排序 基本介绍 大顶堆举例说明 堆排序的基本思想: 简单的思路 代码实现 将一个数组(二叉树), 调整成一个大顶堆 //编写一个堆排序的方法 完整代码 总结: 图解: 基本介绍 堆排序是利用堆这种数据结构二设计的一种排序算法,堆排序是一种选择排序,他的最好最坏,平均复杂度都为O(nlogn)， 它也是不稳定排序 堆是具有一下性质的完全二叉树:每个节点的值都大于或者等于其左右孩子节点的值 堆排序的基本思想: 将待排序序列构造成一个大顶堆 此时,整个序列的最大值就是堆顶的根节点 将其与末尾元素进行交换， 此时末尾就为最大值 然后将剩余的n-1个元素重新构造一个堆,这样会得到n个元素的次小值 } } //当for 循环结束后，我们已经将以i 为父结点的树的最大值，放在了 最顶(局部) arr[i] = temp;//将temp值放到调整后的位置 } //编写一个堆排序的方法 public static void heapSort(int arr[]) { int temp = 0; System.out.println("堆排序!!")
59520发布于 2021-04-22 - 来自专栏专注研发
选择排序—堆排序（Heap Sort） 没看明白，不解释
堆排序是一种树形选择排序，是对直接选择排序的有效改进。 基本思想： 堆的定义如下：具有n个元素的序列（k1,k2,...,kn),当且仅当满足 ? 时称之为堆。 称这个过程为堆排序。 因此，实现堆排序需解决两个问题： 1. 如何将n 个待排序的数建成堆； 2. 输出堆顶元素后，怎样调整剩余n-1 个元素，使其成为一个新堆。 算法的实现： 从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。 i= (length -1) / 2 for (int i = (length -1) / 2 ; i >= 0; --i) HeapAdjust(H,i,length); } /** * 堆排序算法 而建堆时的比较次数不超过4n 次，因此堆排序最坏情况下，时间复杂度也为：O(nlogn )。
90320发布于 2018-09-21 - 来自专栏AI那点小事
09-排序3 Insertion or Heap Sort (25分)
Heap sort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted Output Specification: For each test case, print in the first line either “Insertion Sort” or “Heap Sort a[parent] = x; } void swap(int* a ,int* b) { int tmp = *a; *a = *b; *b = tmp; } bool Heap_Sort [i] = A[i]; } for ( int i = 0 ; i < len ; i++){ cin>>B[i]; } bool isHeap = Heap_Sort return false; } //返回下一次进行堆排序操作的元素的下标。
49820发布于 2020-04-18 - 来自专栏常用算法专栏
【数据结构面试】堆排序（Heap Sort）Java实现（2026最新）：时间复杂度、空间复杂度与稳定性全解析
堆排序提供了一个巧妙的答案：先将这堆数字组织成一种特殊的树形结构——堆（Heap）。在这个结构中，最大（或最小）的元素总是位于树的根部，唾手可得。 有趣的是，Williams发明堆排序的初衷并非为了排序本身，而是为了提供一种高效构建和维护堆（Heap）。堆是一种基于完全二叉树的抽象数据类型，是实现优先队列（PriorityQueue）的理想结构。 第二章：核心思想与数学推演2.1算法原理堆排序分为两个主要阶段：建堆（Heapify）将无序的输入数组原地构建成一个最大堆（Max-Heap）。 作为内省排序（Introsort）：现代C++标准库的std::sort就采用了Introsort，它以快速排序开始，当递归深度超过阈值（可能退化为O(n²)）时，自动切换到堆排序以保证O(nlogn) (String[]args){int[]arr={4,10,3,5,1};System.out.println("Original:"+java.util.Arrays.toString(arr));sort
7520编辑于 2026-04-19 - 来自专栏JavaEdge
插入排序—直接插入排序(Straight Insertion Sort)2. 插入排序—希尔排序（Shell`s Sort）4. 选择排序—堆排序（Heap Sort）
,Collections.sort即是如此设计 相等时不往前插入情况下,可以保持稳定性!!! 2. 选择排序—堆排序（Heap Sort） 一种树形选择排序，是对直接选择排序的有效改进 思想 堆的定义如下：具有n个元素的序列（k1,k2,...,kn),当且仅当满足 ? 称这个过程为堆排序。 因此，实现堆排序需解决两个问题： 1. 如何将n 个待排序的数建成堆； 2. 输出堆顶元素后，怎样调整剩余n-1 个元素，使其成为一个新堆。 所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。 而建堆时的比较次数不超过4n 次，因此堆排序最坏情况下，时间复杂度也为：O(nlogn )。
1.7K71发布于 2018-05-16 - 来自专栏fangyangcoder
算法导论中的四种基本排序
2.3 堆排序 堆排序涉及到的知识比较多，它主要分为三部分：MAX-HESPIFY，BUILD-MAX-HEAP 和 HEAPSORT MAX-HESPIFY：维持最大堆的性质。 -1);//归并排序 25 sort1.display(b,num); 26 cout << "heap_sort:\n"; 27 sort1.heap_sort(c,num);//堆排序 a[], int i); //最大堆排序中的核心，维护最大堆的性质，即父类节点大于子类节点 15 void build_max_heap (int a[], int n); 堆排序 25 26 }; 27 28 #endif 4.3 fy_sort.cpp 1 #include "fy_sort.h" 2 #include<iostream> 3 ::heap_sort (int a[], int n) 121 { 122 build_max_heap (a, n); 123 //实现的是原址排序，将最大堆转化成从小到大的数组
71020发布于 2018-09-11 - 来自专栏数据结构和算法
Python算法——堆排序
堆排序（Heap Sort）是一种基于二叉堆数据结构的排序算法，它通过将元素构建成一个最大堆或最小堆，然后重复从堆中移除根节点，直到堆为空，从而得到有序数组。 = i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest) def heap_sort heap_sort 函数用于构建最大堆和执行堆排序。 = i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest) def heap_sort ): arr[i], arr[0] = arr[0], arr[i] heapify(arr, i, 0) # 测试排序 arr = [9, 6, 5, 2, 8] heap_sort
1K10编辑于 2023-11-30 - 来自专栏Linux系列
数据结构与算法-优化堆排序
(arr) print("Max Heap:", arr) 3. arr[largest] = arr[largest], arr[i] # 交换 optimized_heapify(arr, n, largest) def optimized_heap_sort arr[0], arr[i] # 交换 optimized_heapify(arr, i, 0) # 示例数组 arr = [5, 2, 4, 6, 1, 3] optimized_heap_sort def optimized_heap_sort_mixed(arr): n = len(arr) # 构建最大堆 build_max_heap(arr) # 逐个取出元素 k += 1 arr[k - 1] = key # 示例数组 arr = [5, 2, 4, 6, 1, 3] optimized_heap_sort_mixed
32310编辑于 2024-08-09 - 来自专栏测试开发囤货
Python算法解析：堆排序的娴熟应用，数据排序高手进阶！堆排序
堆排序算法的原理和实现步骤 构建最大堆（Max Heap）：将待排序的列表构建成一个最大堆。最大堆是一个完全二叉树，其中每个节点的值都大于或等于其子节点的值。 = i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest) def heap_sort arr[i], arr[0] = arr[0], arr[i] heapify(arr, i, 0) # 测试示例 nums = [64, 25, 12, 22, 11] heap_sort (nums) print("排序后的数组:", nums) 在这个示例中，我们定义了两个函数：heapify和heap_sort。 函数heap_sort用于执行堆排序算法，首先构建最大堆，然后逐步将最大值交换到列表的末尾，最后得到排序好的列表。
39130编辑于 2023-08-08 - 来自专栏solr lucene源码解析
shallow heap和retained heap
在解释这两个名词之前，需要说明一下：JAVA对象大小=对象头+实例数据+对齐填充 shallow heap为对象自身占用的内存大小，不包括它引用的对象的大小 shallow heap 非数组类型的对象的 shallow heap shallow_size=对象头+各成员变量大小之和+对齐填充 其中，各成员变量大小之和就是实例数据，如果存在继承的情况，需要包括父类成员变量 注意：不包含所引用的对象的本身的大小 数组长度+对齐填充，如果是引用类型，则是四字节或者八字节（64位系统）， 如果是boolean类型，则是一个字节 注意：这里 类型变量大小*数组长度 就是实例数据，强调是变量不是对象本身 retained heap retained heap大小为对象本身和其所引用的对象大小之和 换个说法就是当前对象被GC后，从Heap上总共能释放掉的内存，强调是GC后能释放的。
1.4K00发布于 2019-08-18 - 来自专栏老高的技术博客
python 堆排序算法
老高最近在准备面试，正好复习到堆排序，正好总结一下 堆排序的算法思路基本如下： 找到最后一个非叶子节点，进行第一次循环比较，找到第一个最值 将找到的最值移动到末尾，长度-1，root=0，继续排序n-1 次 每次发生比较后需要在此循环比较，直到没有发生移动或者超过最大长度 比较的时间复杂度O(lgn)，生成堆的时间复杂度为O(n)，所以总的时间复杂度为O(nlgn) 堆排序是不稳定的排序 def build_heap (h, size, min) def heap_sort(l): build_heap(l) l_len = len(l) for i in range(l_len - 1 , -1, -1): l[0], l[i] = l[i], l[0] re_heap(l, i, 0) return l def heap_sort_min( , 6, 34, 67, 475, 545, 567, 3454] print heap_sort(l) print '-' * 36 print heap_sort_min(l
43520编辑于 2022-12-28 堆(heap)
，则将子节点的值上移 if (temp < maxHeap.heap[child]) { maxHeap.heap[child / 2] = maxHeap.heap MaxHeap mh; mh.heap = heap; mh.MaxSize = 10; mh.size = 5; get_maxHeap(mh); // 初始化最大堆 [child / 2] < val) { maxHeap.heap[child] = maxHeap.heap[child / 2]; child = child / 2 几种高效的排序总结： 堆排序 复杂度分析 时间复杂度：O(n)，其中 n 是堆中元素的数量。 空间复杂度：O(1)，只使用了常数级的额外空间。 )详解-堆的建立、插入、删除、最大堆、最小堆、堆排序等 ....
44510编辑于 2025-10-22- 来自专栏Linux系列
数据结构与算法-关于堆的基本排序介绍
arr[i], arr[largest] = arr[largest], arr[i] # 交换 heapify(arr, n, largest) def build_max_heap in range(n // 2 - 1, -1, -1): heapify(arr, n, i) # 示例数组 arr = [5, 2, 4, 6, 1, 3] build_max_heap (arr) print("Max Heap:", arr) 3. def heap_sort(arr): n = len(arr) # 构建最大堆 build_max_heap(arr) # 逐个取出元素 for i in arr[i], arr[0] = arr[0], arr[i] # 交换 heapify(arr, i, 0) # 示例数组 arr = [5, 2, 4, 6, 1, 3] heap_sort
37310编辑于 2024-08-09 - 来自专栏深度学习思考者
Python学习（三） 八大排序算法的实现（下）
本文Python实现了插入排序、基数排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序的后面四种。 描述 堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。 adjust_heap(lists,i,count) def adjust_heap(lists,i,n): j = i*2 +1 while j < n: if j+ def heap_sort( lists ): count = len( lists ) build_heap( lists ) #交换堆顶与最后一个结点,再调整堆 for lists, 0, i ) return lists lists = [-3, 1, 3, 0, 9, 7] print heap_sort(lists) 4.归并排序 描述 归并排序是建立在归并操作上的一种有效的排序算法
839100发布于 2018-01-03 - 来自专栏全栈程序员必看
算法 – 堆排序（C#）
} Console.WriteLine("\r\n"); Console.WriteLine("In Heap Sort:"); HeapSort(a); Console.WriteLine(""); Console.WriteLine("After Heap Sort:"); Console.Write(i + " "); } Console.WriteLine("\r\nMax heap in each heap sort Sort: 1 14 6 2 8 66 9 3 0 10 5 34 76 809 4 7 In Heap Sort: Build max heap: 809 14 76 7 10 66 9 3 0 8 5 34 1 6 4 2 Max heap in each heap sort iteration: 76 14 66 7 10 34 9 3 0 8 5 2 1 6 4 66 14 34 7 10
36720编辑于 2022-09-14 - 来自专栏小阿祥架构专栏
【算法】核心排序算法之堆排序原理及实战
1.什么是堆排序指利用堆这种数据结构所设计的一种排序算法，将二叉堆的数据进行排序，构建一个有序的序列排序过程中，只需要个【别临时存储】空间，所以堆排序是原地排序算法，空间复杂度为O(1)本身大顶堆和小顶堆里面的元素是无序的 n个元素的次小值反复执行上述步骤，得到一个有序的数组2.编码实现无序堆构建成二叉堆利用二叉堆特性：数组索引一半后的都是叶子节点，不需要做下沉比较；一半前都是非叶子节点，才需要做下沉比较图片/** * 堆排序 */public class HeapSort { public static void sort(int[] arr){ //1.构建堆，数组下标0不存储数据 int )/2; i > 0; i--) { down(heap,i,heap.length - i); } //4.堆排序，把堆顶元素和数组最后一个索引元素交换 HeapSort.sort(arr); //输出排序后数组中的元素 System.out.println("堆排序:"+ Arrays.toString(arr
65500编辑于 2023-05-28 - 来自专栏Python碎片公众号的专栏
Python实现堆排序
一、堆排序简介 堆排序(Heap Sort)是利用堆这种数据结构所设计的一种排序算法。 三、Python实现堆排序 # coding=utf-8 def heap_sort(array): first = len(array) // 2 - 1 for start in range break if __name__ == '__main__': array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21] print(heap_sort 实现堆排序函数heap_sort(array)时，先调用big_heap(array, start, end)函数循环对非叶子节点进行调整，构造大顶堆，然后将堆顶和堆尾交换，将堆尾从堆中取出，添加到已排序序列中 四、堆排序的时间复杂度和稳定性 1. 时间复杂度 在堆排序中，构建一次大顶堆可以取出一个元素，完成一轮堆排序，一共需要进行n轮堆排序。
1.6K40发布于 2021-02-26
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号